package com.turing.common.util;

import java.util.ArrayList;
import java.util.List;

/*
 * O(N) = N*LogN
 * 10w个节点, 非排序插入263s
 * 1w个节点, 排序插入花费1.6s, 非排序插入花费910ms
 * 1k个节点，排序插入花费81ms, 非排序插入花费10ms
 * 100个节点，排序插入花费40ms, 非排序插入花费1ms
 * 通过ergodicTree()方法不断添加子节点, 构造出树
 * 需要先初始化一个rootNode节点
 * */
public abstract class TreeNode {

    private List<TreeNode> childNodes;

    /*
     * 获得一棵排好序的树
     * */
    public void ergodicTreeOrdered(TreeNode rootNode, TreeNode childNode) {
        ergodicTree(rootNode, childNode);
        sortTree(rootNode);
    }

    /*
     * 添加子节点
     * */
    public void ergodicTree(TreeNode rootNode, TreeNode childNode) {

        if (isChildNode(rootNode, childNode)) {
            addChildNode(rootNode, childNode);
        } else {
            if (hasNextLevel(rootNode)) {
                List<TreeNode> childs = rootNode.getChildNodes();
                for (int i = 0; i < childs.size(); i++) {
                    ergodicTree(childs.get(i), childNode);
                }
            }
        }

    }

    /*
     * 对树进行排序
     * */
    public void sortTree(TreeNode rootNode) {

        if (rootNode != null && rootNode.getChildNodes() != null) {

            rootNode.getChildNodes().sort(this::compareTo);

            for (int i = 0; i < rootNode.getChildNodes().size(); i++) {
                sortTree(rootNode.getChildNodes().get(i));
            }
        }
    }

    /*
     * 子类必须重写该比较方法
     * */
    public abstract boolean isChildNode(TreeNode rootNode, TreeNode childNode);

    /*
     * 需要重写排序方法
     * */
    public abstract int compareTo(TreeNode firstNode, TreeNode secondNode);

    private static void addChildNode(TreeNode parentNode, TreeNode childNode) {
        if (hasNextLevel(parentNode)) {
            parentNode.getChildNodes().add(childNode);
            return;
        }

        List<TreeNode> childNodes = new ArrayList<>();
        childNodes.add(childNode);
        parentNode.setChildNodes(childNodes);
    }

    private static boolean hasNextLevel(TreeNode parentNode) {
        if (parentNode != null) {
            if (parentNode.getChildNodes() != null && parentNode.getChildNodes().size() > 0) {
                return true;
            }
        }

        return false;
    }

    public List<TreeNode> getChildNodes() {
        return childNodes;
    }

    public void setChildNodes(List<TreeNode> childNodes) {
        this.childNodes = childNodes;
    }
}
